package org.nowcoder.leetcode.sort;

import java.util.PriorityQueue;

/**
 * Title  : 973. K Closest Points to Origin
 * Source : https://leetcode.cn/problems/k-closest-points-to-origin/description
 * Author : XrazYang
 * Date   : 2023-09-20
 */

public class LeetCode_973 {
    private class ClosestElement {
        private int[] point;
        private int dis;

        protected ClosestElement(int[] point, int dis) {
            this.point = point;
            this.dis = dis;
        }
    }

    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<ClosestElement> minHeap = new PriorityQueue<>(k, (o1, o2) -> o2.dis - o1.dis);
        for (int[] point : points) {
            int dis = point[0] * point[0] + point[1] * point[1];
            ClosestElement element = new ClosestElement(point, dis);
            if (minHeap.size() < k) {
                minHeap.offer(element);
            } else {
                if (minHeap.peek().dis > dis) {
                    minHeap.poll();
                    minHeap.offer(element);
                }
            }

        }
        int[][] results = new int[k][2];
        for (int i = 0; i < k; i++) {
            results[i] = minHeap.poll().point;
        }
        return results;
    }
}
